home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / circular.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  15.6 KB  |  622 lines
  1. /*
  2.   File: CircularList.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12. */
  13.   
  14. package collections;
  15.  
  16. import java.util.Enumeration;
  17. import java.util.NoSuchElementException;
  18.  
  19. /**
  20.  *
  21.  * Circular linked lists. Publically Implement only those
  22.  * methods defined in interfaces.
  23.  *
  24.  * @author Doug Lea
  25.  * @version 0.93
  26.  *
  27.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  28. **/
  29.  
  30.  
  31. public class CircularList extends UpdatableSeqImpl implements UpdatableSeq {
  32.  
  33. // instance variables
  34.  
  35. /**
  36.  * The head of the list. Null if empty
  37. **/
  38.   protected CLCell list_;
  39.  
  40. // constructors
  41.  
  42. /**
  43.  * Make an empty list with no element screener
  44. **/
  45.  
  46.   public CircularList() { this(null, null, 0); }
  47.  
  48. /**
  49.  * Make an empty list with supplied element screener
  50. **/
  51.   public CircularList(Predicate screener) { this(screener, null, 0); }
  52.  
  53. /**
  54.  * Special version of constructor needed by clone()
  55. **/
  56.  
  57.   protected CircularList(Predicate s, CLCell h, int c) { 
  58.     super(s); list_ = h; count_ = c;
  59.   }
  60.  
  61. /**
  62.  * Make an independent copy of the list. Elements themselves are not cloned
  63. **/
  64.  
  65.   protected Object clone() throws CloneNotSupportedException { 
  66.     if (list_ == null) return new CircularList(screener_, null, 0);
  67.     else return new CircularList(screener_, list_.copyList(), count_);  
  68.   }
  69.  
  70.  
  71. // Collection methods
  72.  
  73. /**
  74.  * Implements collections.Collection.includes.
  75.  * Time complexity: O(n).
  76.  * @see collections.Collection#includes
  77. **/
  78.   public synchronized boolean includes(Object element) {
  79.     if (element == null || list_ == null) return false;
  80.     return list_.find(element) != null;
  81.   }
  82.  
  83. /**
  84.  * Implements collections.Collection.occurrencesOf.
  85.  * Time complexity: O(n).
  86.  * @see collections.Collection#occurrencesOf
  87. **/
  88.   public synchronized int occurrencesOf(Object element) {
  89.     if (element == null || list_ == null) return 0;
  90.     return list_.count(element);
  91.   }
  92.  
  93. /**
  94.  * Implements collections.Collection.elements.
  95.  * Time complexity: O(1).
  96.  * @see collections.Collection#elements
  97. **/
  98.   public synchronized CollectionEnumeration elements() { 
  99.     return new CLEnumeration(this, list_); 
  100.   }
  101.  
  102.  
  103. // Seq methods
  104.  
  105. /**
  106.  * Implements collections.Seq.first.
  107.  * Time complexity: O(1).
  108.  * @see collections.Seq#first
  109. **/
  110.   public synchronized Object first()
  111.   throws  NoSuchElementException {
  112.     return firstCell().element();   
  113.   }
  114.  
  115. /**
  116.  * Implements collections.Seq.last.
  117.  * Time complexity: O(1).
  118.  * @see collections.Seq#last
  119. **/
  120.   public synchronized Object last()
  121.   throws  NoSuchElementException {
  122.     return lastCell().element();  
  123.   }
  124.  
  125. /**
  126.  * Implements collections.Seq.at.
  127.  * Time complexity: O(n).
  128.  * @see collections.Seq#at
  129. **/
  130.   public synchronized Object at(int index) 
  131.     throws  NoSuchElementException {
  132.     return cellAt(index).element();  
  133.   }
  134.  
  135. /**
  136.  * Implements collections.Seq.firstIndexOf.
  137.  * Time complexity: O(n).
  138.  * @see collections.Seq#firstIndexOf
  139. **/
  140.   public synchronized int firstIndexOf(Object element, int startingIndex) {
  141.     if (startingIndex < 0) startingIndex = 0;
  142.     CLCell p = list_;
  143.     if (p == null || element == null) return -1;
  144.     for (int i = 0; true; ++i) {
  145.       if (i >= startingIndex && p.element().equals(element)) return i;
  146.       p = p.next(); 
  147.       if (p == list_) return -1;
  148.     }
  149.   }
  150.  
  151.  
  152. /**
  153.  * Implements collections.Seq.lastIndexOf.
  154.  * Time complexity: O(n).
  155.  * @see collections.Seq#lastIndexOf
  156. **/
  157.   public synchronized int lastIndexOf(Object element, int startingIndex) {
  158.     if (element == null || count_ == 0) return -1;
  159.     if (startingIndex >= size()) startingIndex = size() -1;
  160.     if (startingIndex < 0) startingIndex = 0;
  161.     CLCell p = cellAt(startingIndex);
  162.     int i = startingIndex;
  163.     for (;;) {
  164.       if (p.element().equals(element)) return i;
  165.       else if (p == list_) return -1;
  166.       else {
  167.         p = p.prev();
  168.         --i;
  169.       }
  170.     }
  171.   }
  172.  
  173. /**
  174.  * Implements collections.Seq.firstIndexOf.
  175.  * Time complexity: O(n).
  176.  * @see collections.Seq#firstIndexOf
  177. **/
  178.   public synchronized int firstIndexOf(Object element) {
  179.     return firstIndexOf(element, 0);
  180.   }
  181.  
  182. /**
  183.  * Implements collections.Seq.lastIndexOf.
  184.  * Time complexity: O(n).
  185.  * @see collections.Seq#lastIndexOf
  186. **/
  187.   public synchronized int lastIndexOf(Object element) {
  188.     return lastIndexOf(element, size()-1);
  189.   }
  190.  
  191.  
  192. /**
  193.  * Implements collections.Seq.subseq.
  194.  * Time complexity: O(length).
  195.  * @see collections.Seq#subseq
  196. **/
  197.   public synchronized /* CircularList */ Seq subseq(int from, int length) 
  198.   throws  NoSuchElementException {
  199.     if (length > 0) {
  200.       checkIndex(from);
  201.       CLCell p = cellAt(from);
  202.       CLCell newlist = new CLCell(p.element());
  203.       CLCell current = newlist;
  204.       for (int i = 1; i < length; ++i) {
  205.         p = p.next();
  206.         if (p == null) checkIndex(from+i); // force exception
  207.         current.addNext(p.element());
  208.         current = current.next();
  209.       }
  210.       return new CircularList(screener_, newlist, length);
  211.     }
  212.     else
  213.       return new CircularList();
  214.   }
  215.  
  216. // UpdatableCollection methods
  217.  
  218. /**
  219.  * Implements collections.UpdatableCollection.clear.
  220.  * Time complexity: O(1).
  221.  * @see collections.UpdatableCollection#clear
  222. **/
  223.   public synchronized void clear() { 
  224.     list_ = null; 
  225.     setCount(0); 
  226.   }
  227.  
  228. /**
  229.  * Implements collections.UpdatableCollection.exclude.
  230.  * Time complexity: O(n).
  231.  * @see collections.UpdatableCollection#exclude
  232. **/
  233.   public synchronized void exclude(Object element)  { 
  234.     remove_(element, true);
  235.   }
  236.  
  237. /**
  238.  * Implements collections.UpdatableCollection.removeOneOf.
  239.  * Time complexity: O(n).
  240.  * @see collections.UpdatableCollection#removeOneOf
  241. **/
  242.   public synchronized void removeOneOf(Object element) {
  243.     remove_(element, false);
  244.   }
  245.  
  246. /**
  247.  * Implements collections.UpdatableCollection.replaceOneOf
  248.  * Time complexity: O(n).
  249.  * @see collections.UpdatableCollection#replaceOneOf
  250. **/
  251.   public synchronized void replaceOneOf(Object oldElement, Object newElement)  throws IllegalElementException { 
  252.     replace_(oldElement, newElement, false);
  253.   }
  254.  
  255. /**
  256.  * Implements collections.UpdatableCollection.replaceAllOf.
  257.  * Time complexity: O(n).
  258.  * @see collections.UpdatableCollection#replaceAllOf
  259. **/
  260.   public synchronized void replaceAllOf(Object oldElement, 
  261.                                                  Object newElement)  
  262.   throws IllegalElementException { 
  263.     replace_(oldElement, newElement, true);
  264.   }
  265.  
  266.  
  267. /**
  268.  * Implements collections.UpdatableCollection.take.
  269.  * Time complexity: O(1).
  270.  * takes the last element on the list.
  271.  * @see collections.UpdatableCollection#take
  272. **/
  273.   public synchronized Object take() 
  274.   throws  NoSuchElementException {
  275.     Object v = last();
  276.     removeLast();
  277.     return v;
  278.   }
  279.  
  280.  
  281.  
  282. // UpdatableSeq methods
  283.  
  284. /**
  285.  * Implements collections.UpdatableSeq.insertFirst.
  286.  * Time complexity: O(1).
  287.  * @see collections.UpdatableSeq#insertFirst
  288. **/
  289.   public synchronized void insertFirst(Object element) 
  290.   throws IllegalElementException {
  291.     checkElement(element);
  292.     if (list_ == null) list_ = new CLCell(element);
  293.     else list_ = list_.addPrev(element);
  294.     incCount();
  295.   }
  296.  
  297. /**
  298.  * Implements collections.UpdatableSeq.replaceFirst.
  299.  * Time complexity: O(1).
  300.  * @see collections.UpdatableSeq#replaceFirst
  301. **/
  302.   public synchronized void replaceFirst(Object element) 
  303.   throws IllegalElementException {
  304.     checkElement(element);
  305.     firstCell().element(element);
  306.     incVersion();
  307.   }
  308.  
  309. /**
  310.  * Implements collections.UpdatableSeq.removeFirst.
  311.  * Time complexity: O(1).
  312.  * @see collections.UpdatableSeq#removeFirst
  313. **/
  314.   public synchronized void removeFirst()
  315.   throws NoSuchElementException {
  316.     if (firstCell().isSingleton()) 
  317.       list_ = null;
  318.     else {
  319.       CLCell n = list_.next();
  320.       list_.unlink();
  321.       list_ = n;
  322.     }
  323.     decCount();
  324.   }
  325.  
  326. /**
  327.  * Implements collections.UpdatableSeq.insertLast.
  328.  * Time complexity: O(1).
  329.  * @see collections.UpdatableSeq#insertLast
  330. **/
  331.   public synchronized void insertLast(Object element) 
  332.   throws IllegalElementException {
  333.     if (list_ == null) insertFirst(element);
  334.     else { 
  335.       checkElement(element);
  336.       list_.prev().addNext(element); 
  337.       incCount(); 
  338.     }
  339.   }
  340.  
  341. /**
  342.  * Implements collections.UpdatableSeq.replaceLast.
  343.  * Time complexity: O(1).
  344.  * @see collections.UpdatableSeq#replaceLast
  345. **/
  346.   public synchronized void replaceLast(Object element) 
  347.   throws IllegalElementException, NoSuchElementException {
  348.     checkElement(element);
  349.     lastCell().element(element);
  350.     incVersion();
  351.   }
  352.  
  353.  
  354. /**
  355.  * Implements collections.UpdatableSeq.removeLast.
  356.  * Time complexity: O(1).
  357.  * @see collections.UpdatableSeq#removeLast
  358. **/
  359.   public synchronized void removeLast() 
  360.   throws NoSuchElementException {
  361.     CLCell l = lastCell();
  362.     if (l == list_) list_ = null;
  363.     else l.unlink();
  364.     decCount();
  365.   }
  366.  
  367. /**
  368.  * Implements collections.UpdatableSeq.insertAt.
  369.  * Time complexity: O(n).
  370.  * @see collections.UpdatableSeq#insertAt
  371. **/
  372.   public synchronized void insertAt(int index, Object element) 
  373.   throws IllegalElementException, NoSuchElementException {
  374.     if (index == 0) insertFirst(element);
  375.     else { 
  376.       checkElement(element);
  377.       cellAt(index - 1).addNext(element); 
  378.       incCount(); 
  379.     }
  380.   }
  381.     
  382. /**
  383.  * Implements collections.UpdatableSeq.replaceAt.
  384.  * Time complexity: O(n).
  385.  * @see collections.UpdatableSeq#replaceAt
  386. **/
  387.   public synchronized void replaceAt(int index, Object element) 
  388.   throws IllegalElementException, NoSuchElementException {
  389.     checkElement(element);
  390.     cellAt(index).element(element);
  391.     incVersion();
  392.   }
  393.  
  394. /**
  395.  * Implements collections.UpdatableSeq.removeAt.
  396.  * Time complexity: O(n).
  397.  * @see collections.UpdatableSeq#removeAt
  398. **/
  399.   public synchronized void removeAt(int index) 
  400.   throws NoSuchElementException {
  401.     if (index == 0) removeFirst();
  402.     else { 
  403.       cellAt(index - 1).unlinkNext(); 
  404.       decCount(); 
  405.     }
  406.   }
  407.  
  408. /**
  409.  * Implements collections.UpdatableSeq.prependElements.
  410.  * Time complexity: O(number of elements in e).
  411.  * @see collections.UpdatableSeq#prependElements
  412. **/
  413.   public synchronized void prependElements(Enumeration e) 
  414.   throws IllegalElementException, CorruptedEnumerationException {
  415.     CLCell hd = null;
  416.     CLCell current = null;
  417.     while (e.hasMoreElements()) {
  418.       Object element = e.nextElement();
  419.       checkElement(element);
  420.       incCount();
  421.       if (hd == null) {
  422.         hd = new CLCell(element);
  423.         current = hd;
  424.       }
  425.       else {
  426.         current.addNext(element);
  427.         current = current.next();
  428.       }
  429.     }
  430.     if (list_ == null)
  431.       list_ = hd;
  432.     else if (hd != null) {
  433.       CLCell tl = list_.prev();
  434.       current.next(list_); list_.prev(current);
  435.       tl.next(hd); hd.prev(tl);
  436.       list_ = hd;
  437.     }
  438.   }
  439.  
  440. /**
  441.  * Implements collections.UpdatableSeq.appendElements.
  442.  * Time complexity: O(number of elements in e).
  443.  * @see collections.UpdatableSeq#appendElements
  444. **/
  445.   public synchronized void appendElements(Enumeration e) 
  446.   throws IllegalElementException, CorruptedEnumerationException {
  447.     if (list_ == null) prependElements(e);
  448.     else {
  449.       CLCell current = list_.prev();
  450.       while (e.hasMoreElements()) {
  451.         Object element = e.nextElement();
  452.         checkElement(element);
  453.         incCount();
  454.         current.addNext(element);
  455.         current = current.next();
  456.       }
  457.     }
  458.   }
  459.  
  460. /**
  461.  * Implements collections.UpdatableSeq.insertElementsAt.
  462.  * Time complexity: O(size() + number of elements in e).
  463.  * @see collections.UpdatableSeq#insertElementsAt
  464. **/
  465.   public synchronized void insertElementsAt(int index, Enumeration e) 
  466.   throws IllegalElementException, CorruptedEnumerationException,
  467.   NoSuchElementException {
  468.     if (list_ == null || index == 0) prependElements(e);
  469.     else {
  470.       CLCell current = cellAt(index - 1);
  471.       while (e.hasMoreElements()) {
  472.         Object element = e.nextElement();
  473.         checkElement(element);
  474.         incCount();
  475.         current.addNext(element);
  476.         current = current.next();
  477.       }
  478.     }
  479.   }
  480.  
  481.  
  482. /**
  483.  * Implements collections.UpdatableSeq.removeFromTo.
  484.  * Time complexity: O(n).
  485.  * @see collections.UpdatableSeq#removeFromTo
  486. **/
  487.   public synchronized void removeFromTo(int fromIndex, int toIndex) 
  488.   throws NoSuchElementException {
  489.     checkIndex(toIndex);
  490.     CLCell p = cellAt(fromIndex);
  491.     CLCell last = list_.prev();
  492.     for (int i = fromIndex; i <= toIndex; ++i) {
  493.       decCount();
  494.       CLCell n = p.next();
  495.       p.unlink();
  496.       if (p == list_) {
  497.         if (p == last) {
  498.           list_ = null;
  499.           return;
  500.         }
  501.         else
  502.           list_ = n;
  503.       }
  504.       p = n;
  505.     }
  506.   }
  507.     
  508.  
  509. // helper methods
  510.  
  511. /**
  512.  * return the first cell, or throw exception if empty
  513. **/
  514.   private CLCell firstCell() throws NoSuchElementException { 
  515.     if (list_ != null) return list_; 
  516.     checkIndex(0);
  517.     return null; // not reached!
  518.  
  519.   }
  520.  
  521. /**
  522.  * return the last cell, or throw exception if empty
  523. **/
  524.   private CLCell lastCell() throws NoSuchElementException { 
  525.     if (list_ != null) return list_.prev();
  526.     checkIndex(0);
  527.     return null; // not reached!
  528.   }
  529.  
  530. /**
  531.  * return the index'th cell, or throw exception if bad index
  532. **/
  533.   private CLCell cellAt(int index) throws NoSuchElementException {
  534.     checkIndex(index);
  535.     return list_.nth(index);
  536.   }
  537.  
  538. /**
  539.  * helper for remove/exclude
  540. **/
  541.   private void remove_(Object element, boolean allOccurrences) 
  542.   throws IllegalElementException {
  543.     if (element == null || list_ == null) return;
  544.     CLCell p = list_;
  545.     for (;;) {
  546.       CLCell n = p.next();
  547.       if (p.element().equals(element)) {
  548.         decCount();
  549.         p.unlink();
  550.         if (p == list_) {
  551.           if (p == n) {
  552.             list_ = null;
  553.             break;
  554.           }
  555.           else list_ = n;
  556.         }
  557.         if (!allOccurrences) break;
  558.         else p = n;
  559.       }
  560.       else if (n == list_)
  561.         break;
  562.       else
  563.         p = n;
  564.     } 
  565.   }
  566.  
  567.  
  568. /**
  569.  * helper for replace*
  570. **/
  571.   private void replace_(Object oldElement, Object newElement, 
  572.                           boolean allOccurrences)  
  573.   throws IllegalElementException { 
  574.     if (oldElement == null || list_ == null) return;
  575.     CLCell p = list_; 
  576.     do { 
  577.       if (p.element().equals(oldElement)) {
  578.         checkElement(newElement);
  579.         incVersion();
  580.         p.element(newElement);
  581.         if (!allOccurrences) return;
  582.       }
  583.       p = p.next(); 
  584.     } while (p != list_); 
  585.   }
  586.  
  587. // ImplementationCheckable methods
  588.  
  589. /**
  590.  * Implements collections.ImplementationCheckable.checkImplementation.
  591.  * @see collections.ImplementationCheckable#checkImplementation
  592. **/
  593.  
  594.   public synchronized void checkImplementation() 
  595.   throws ImplementationError {
  596.  
  597.     super.checkImplementation();
  598.  
  599.     assert(((count_ == 0) == (list_ == null)));
  600.     assert((list_ == null || list_.length() == count_));
  601.  
  602.     if (list_ == null) return;
  603.  
  604.     int c = 0;
  605.     CLCell p = list_;
  606.     do {
  607.       assert(p.prev().next() == p);
  608.       assert(p.next().prev() == p);
  609.       assert(canInclude(p.element()));
  610.       assert(occurrencesOf(p.element()) > 0);
  611.       assert(includes(p.element()));
  612.       p = p.next();
  613.       ++c;
  614.     }
  615.     while (p != list_);
  616.     
  617.     assert(c == count_);
  618.  
  619.   }
  620. }
  621.  
  622.